import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Board {

	private class Block {
		public int i;
		public int j;

		public Block(int i, int j) {
			super();
			this.i = i;
			this.j = j;
		}

		public Block getNorthNeighbor() {
			if (i - 1 >= 0) {
				return new Block(i - 1, j);
			}
			return null;
		}

		public Block getSouthNeighbor() {
			if (i + 1 < dimension) {
				return new Block(i + 1, j);
			}
			return null;
		}

		public Block getEastNeighbor() {
			if (j + 1 < dimension) {
				return new Block(i, j + 1);
			}
			return null;
		}

		public Block getWestNeighbor() {
			if (j - 1 >= 0) {
				return new Block(i, j - 1);
			}
			return null;
		}
	}

	private int[][] blocks;
	private int dimension;
	private int manhattan = -1;
	private int hamming = -1;

	// (where blocks[i][j] = block in row i, column j)
	public Board(int[][] blocks) {
		this.dimension = blocks.length;
		this.blocks = blocksCopy(blocks);
	}

	// board dimension N
	public int dimension() {
		return dimension;
	}

	// is this board the goal board?
	public boolean isGoal() {
		if (hamming < 0) {
			this.hamming = hamming();
		}
		return this.hamming == 0;
	}

	// a board obtained by exchanging two adjacent blocks in the same row
	public Board twin() {
		int[][] twin = blocksCopy(blocks);
		
		for (int i = 0; i < dimension; i++) {
			for (int j = 0; j < dimension-1; j++) {
				if (twin[i][j] != 0 && twin[i][j + 1] != 0) {
					int tmp = twin[i][j];
					twin[i][j] = twin[i][j + 1];
					twin[i][j + 1] = tmp;
					return new Board(twin);
				}
			}
		}
		return null;
	}
	
	public int hamming() {
		int numberOfBlocksOutOfPlace = 0;
		for (int i = 0; i < dimension; i++) {
			for (int j = 0; j < dimension; j++) {
				if (isEmptyBlock(i, j)) {
					// skip it
				} else if (isBlockOutOfPlace(i, j)) {
					numberOfBlocksOutOfPlace++;
				}
			}
		}
		return numberOfBlocksOutOfPlace;
	}

	private boolean isEmptyBlock(int i, int j) {
		return blocks[i][j] == 0;
	}

	private boolean isBlockOutOfPlace(int i, int j) {
		return blocks[i][j] != (i * dimension) + (j + 1);
	}

	// sum of Manhattan distances between blocks and goal
	public int manhattan() {
		if (this.manhattan > -1) {
			return this.manhattan;
		} else {
			int manhatan = 0;
			for (int i = 0; i < dimension; i++) {
				for (int j = 0; j < dimension; j++) {
					if (isEmptyBlock(i, j)) {
						// skip it
					} else {
						int srcValue = blocks[i][j];
						Block dst = findDest(srcValue);
						int distance = Math.abs(dst.i - i)
								+ Math.abs(dst.j - j);
						manhatan += distance;
					}
				}
			}
			return manhatan;
		}
	}

	private Block findDest(int srcValue) {
		if (srcValue == 0) {
			return new Block(dimension - 1, dimension - 1);
		}
		for (int i = 0; i < dimension; i++) {
			for (int j = 0; j < dimension; j++) {
				if (srcValue == ((i * dimension) + (j + 1))) {
					return new Block(i, j);
				}
			}
		}
		return null;
	}


	private int[][] blocksCopy(int [][] blocks) {
		int[][] copy = new int[blocks.length][blocks.length];
		for (int i = 0; i < blocks.length; i++) {
			for (int j = 0; j < blocks.length; j++) {
				copy[i][j] = blocks[i][j];
			}
		}
		return copy;
	}
	

	// all neighboring boards
	public Iterable<Board> neighbors() {
		Block emptyBlock = findEmptyBlock();
		java.util.List<Block> neighbors = getNeighbors(emptyBlock);
		return createNeigboringBoards(emptyBlock, neighbors);
	}

	private Iterable<Board> createNeigboringBoards(Block emptyBlock,
			java.util.List<Block> neighborBlocks) {
		List<Board> neighbors = new ArrayList<Board>();
		for (Block block : neighborBlocks) {
			int[][] neighbor = blocksCopy(blocks);
			neighbor[emptyBlock.i][emptyBlock.j] = neighbor[block.i][block.j];
			neighbor[block.i][block.j] = 0;
			neighbors.add(new Board(neighbor));
		}
		return neighbors;
	}

	private java.util.List<Block> getNeighbors(Block emptyBlock) {
		java.util.List<Block> blocks = new ArrayList<Block>();
		Block north = emptyBlock.getNorthNeighbor();
		Block south = emptyBlock.getSouthNeighbor();
		Block east = emptyBlock.getEastNeighbor();
		Block west = emptyBlock.getWestNeighbor();
		if (north != null) {
			blocks.add(north);
		}
		if (south != null) {
			blocks.add(south);
		}
		if (east != null) {
			blocks.add(east);
		}
		if (west != null) {
			blocks.add(west);
		}
		return blocks;
	}

	private Block findEmptyBlock() {
		for (int i = 0; i < dimension; i++) {
			for (int j = 0; j < dimension; j++) {
				if (blocks[i][j] == 0) {
					return new Block(i, j);
				}
			}
		}
		return null;
	}

	@Override
	public String toString() {
		StringBuilder s = new StringBuilder();
		s.append(dimension + "\n");
		for (int i = 0; i < dimension; i++) {
			for (int j = 0; j < dimension; j++) {
				s.append(String.format("%2d ", blocks[i][j]));
			}
			s.append("\n");
		}
		return s.toString();
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Board other = (Board) obj;
		if (!Arrays.deepEquals(blocks, other.blocks))
			return false;
		if (dimension != other.dimension)
			return false;
		return true;
	}
}